// 方法二：贪心
// 用“层序遍历”的思想
//     假设当前位置的最大步数为num
//     那么就可以在接下来对num个数中找最大值，也就是下一次可以走的最大步数
//     用left和right维护每一层的区间，maxpos记录下一层的最右端点
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = 0, maxPos = 0, ret = 0;
        while (left <= right)
        {
            if (maxPos >= n - 1)    //如果能到达的最远位置已经在数组最右边，跳出循环
                break;

            for (int i = left; i <= right; i++)
                maxPos = max(maxPos, i + nums[i]);

            left = right + 1;
            right = maxPos;
            ret++;
        }

        return ret;
    }
};


//方法二：动态规划
//dp[i]表示该位置到结尾所需的最小步数
//从后往前
// class Solution {
// public:
//     int jump(vector<int>& nums) {
//         int n = nums.size();
//         vector<int> dp(n, INT_MAX);
//         dp[n - 1] = 0;
//         for (int i = n - 2; i >= 0; i--)
//         {
//             int maxJump = min(nums[i], n - 1 - i);  // 最大跳跃步数
//             for (int j = 1; j <= maxJump; j++) {
//                 if (dp[i + j] != INT_MAX) {
//                     dp[i] = min(dp[i], dp[i + j] + 1);
//                 }
//             }
                
//         }

//         return dp[0];
//     }
// };